package main

// 221. 最大正方形
// https://leetcode-cn.com/problems/maximal-square/

func maximalSquare(matrix [][]byte) int {
	if len(matrix) == 0 {
		return 0
	}
	dp := make([]int, len(matrix[0])+1)
	maxSide, prev := 0, 0
	for i := 1; i <= len(matrix); i++ {
		for j := 1; j <= len(matrix[0]); j++ {
			temp := dp[j]
			if matrix[i-1][j-1] == '1' {
				dp[j] = min(prev, min(dp[j], dp[j-1])) + 1
				maxSide = max(maxSide, dp[j])
			} else {
				dp[j] = 0
			}
			prev = temp
		}
	}
	return maxSide * maxSide
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	//a := [][]byte{{'1', '1', '0', '1'}, {'1', '1', '0', '1'}, {'1', '1', '1', '1'}}
	a := [][]byte{
		{'1', '1', '1', '1', '1', '1', '1', '1'},
		{'1', '1', '1', '1', '1', '1', '1', '0'},
		{'1', '1', '1', '1', '1', '1', '1', '0'},
		{'1', '1', '1', '1', '1', '0', '0', '0'},
		{'0', '1', '1', '1', '1', '0', '0', '0'}}
	res := maximalSquare(a)
	println(res)
}
